1. Field of the Invention
This invention relates in general to methods and systems involving operations on encrypted data, and more specifically to communication, storage, retrieval, and computation of operations on encrypted data.
2. Description of the Related Art
Various trends in computing and data storage, including cloud computing, are resulting in more and more companies choosing to outsource many of their computational needs to third party data and computation providers. There is a tension, however, between the security of outsourced data and computation and flexibility in handling that data. For this reason, there is a strong desire to be able to encrypt data in such a way that computations can be performed on the encrypted data without needing to first decrypt the data. Researchers have been looking for means to meet this desire for many years, but the general problem has proven difficult. Recent breakthroughs have led to progress in this area, but much work remains to be done to provide practical solutions for even relatively simple cases.
Homomorphic encryption is one technique being used to combat this problem. Almost all homomorphic encryption techniques use asymmetric (i.e. public key) encryption as their base. Asymmetric encryption is orders of magnitude slower to encrypt and decrypt than symmetric encryption, and requires data expansion during encryption to achieve security. Castelluccia et al. (C. Castelluccia, C. Chan, E. Mykletun, and G. Tsudik, Efficient and Provably Secure Aggregation of Encrypted Data in Wireless Sensor Networks. ACM Transactions on Sensor Networks, Vol. 5, No. 3, pp. 20:1-20:36, 2009, herein incorporated by reference in its entirety) recently developed a homomorphic encryption scheme based on symmetric encryption in the context of aggregation in a wireless sensor network. The scheme described in Castellucia et al. provides faster and more compact homomorphic encryption than is possible using a public key-based scheme. Moreover, because of the relative simplicity of the Castellucia et al. scheme, it is able to provide a strong proof of security.
Castelluccia et al. applied its homomorphic encryption scheme to the problem of data aggregation in a wireless network. However, their application involved a fixed computation and no storage.